1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the design of hash CAM (content addressable memory) used in data processing and data communication devices.
2. Background Information
Numerous data processing and data communication applications employ a hash CAM for data look-up. Examples of these applications include but are not limited to network routers and switches looking up forwarding instructions for received frames. FIG. 1 illustrates a typical prior art hash CAM. Prior art hash CAM 100 is constituted with hash function 102, pointer array 104, memory array 106, and comparators 108a-108b. Hash function 102 is used to hash an m-bit input value to an n-bit index, where m and n are positive integers, with m greater than n. An example of hash function 102 is one that breaks the m-bit input into a number of vectors of size less than or equal to n and either EXCLUSIVE-OR all the vectors together, or add all the vectors together. Another example of hash function 102 is one that divides the m-bit input by an nth order polynomial, and uses the n-bit remainder as the index. Pointer array 104 is designed to store up to 2n pointers pointing to 2n starting memory locations of 2n corresponding threaded lists of entries. Each entry includes a comparand, a payload and a next entry pointer (with the xe2x80x9clastxe2x80x9d next entry pointer of each threaded list set to xe2x80x9cnullxe2x80x9d indicating the end of that particular list). Some of these lists may be xe2x80x9cemptyxe2x80x9d, in which case, the corresponding pointers in the pointer array would be xe2x80x9cnullxe2x80x9d. Memory array 106 is designed to store the threaded lists of entries. The payload of an indexed threaded list having the associated comparand that matches the m-bit input or an indication that no match was found is returned. Accordingly, each of the associated comparands is also m-bits in size. The nature of the payloads is application dependent. In the above mentioned network router/switch example, the payloads may be e.g. destination MAC addresses (MAC=media access control) or the number of the physical port to which the intended recipient is attached. Thus, comparator 108a is used to determine if an m-bit comparand matches an m-bit input, while comparator 108b is used to determine if the next pointer is a null pointer or not. Accordingly, comparator 108a is also m-bit in width.
Prior art hash CAMs of the type illustrated in FIG. 1 suffer from the disadvantage that they require large memory arrays and wide comparators for applications involving long input values, i.e. large m. For example, it is not uncommon for many networking applications where the m-bit input may be as long as 128 bits or longer. Thus, a more efficient hash CAM is desired
The novel hash CAM of the present invention comprises a hashing unit and a memory array. The hashing unit is designed to generate an n-bit index in response to an m-bit input, where n and m are positive integers, and n is smaller than m. The memory array is designed to store a number of truncated comparands of size r (in units of bits), and to output a selected one of the stored truncated comparands in accordance with the n-bit index, for comparison with a subset of r selected bits of the m-bit input, where r is also a positive integer, and mxe2x88x92r is less than or equal to n.